package com.kevin.Code.OfferReviewVersion2;

/**
 * @author Vinlee Xiao
 * @Classname LongestIncreasingPathInaMatrix
 * @Description Leetcode 329. 矩阵中的最长递增路径 同剑指Offer 112 困难 深度优先搜索
 * @Date 2022/1/15 16:28
 * @Version 1.0
 */
public class LongestIncreasingPathInaMatrix {

    int[][] pos = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     * 深度优先搜索的方法
     *
     * @param matrix
     * @return
     */
    public int longestIncreasingPath(int[][] matrix) {

        int longest = 0;
        int row = matrix.length;
        int col = matrix[0].length;
        if (row == 0 || col == 0) {
            return 0;
        }

        //里面存储的是到buffer[row][col]坐标的最长路径
        //新建的数组作用是为起缓存的作用
        int[][] buffer = new int[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int length = dfs(matrix, buffer, i, j);
                longest = Math.max(longest, length);
            }
        }
        return longest;
    }

    /**
     * @param matrix
     * @param buffer
     * @param startX
     * @param startY
     * @return
     */
    private int dfs(int[][] matrix, int[][] buffer, int startX, int startY) {
        //递归结束的条件 说明之前的路径已经访问过
        if (buffer[startX][startY] > 0) {
            return buffer[startX][startY];
        }

        int result = 1;
        for (int[] index : pos) {
            int r = index[0];
            int c = index[1];
            int newRow = r + startX;
            int newCol = c + startY;
            if (newRow >= 0 && newRow < matrix.length && newCol >= 0 && newCol < matrix[0].length && matrix[newRow][newCol] > matrix[startX][startY]) {
                int len = dfs(matrix, buffer, newRow, newCol);
                result = Math.max(result, len + 1);
            }
        }
        //对matrxi[startX][startY]赋值
        buffer[startX][startY] = result;
        return result;
    }

}
